Introduction

Primitive roots are special integers that behave like “engines” inside modular arithmetic.
For a prime $p$, a primitive root is an integer that can produce every nonzero number modulo $p$ just by taking powers.

Key ideas to keep in mind:

• We work modulo a prime $p$.
• We only look at the nonzero residues $1,2,\dots,p-1$.
• A primitive root is an integer whose powers cycle through all of these residues.

Why Primitive Roots Matter

Primitive roots matter because they reveal a hidden structure:

• The nonzero numbers modulo $p$ behave like a multiplicative group.
• A primitive root is like a “generator” of this group.
• Many number‑theoretic algorithms rely on primitive roots:
  • Diffie–Hellman key exchange
  • Discrete logarithms
  • Pseudorandom number generation
• They give a compact way to describe all nonzero residues:
  • Instead of listing $1,2,\dots,p-1$, you can list powers of a single number.

Primitive roots turn modular arithmetic into something more predictable and algebraic.

The Multiplicative World Modulo $p$

When $p$ is prime:

• Every nonzero integer modulo $p$ has a multiplicative inverse.
• The set $$\{1,2,\dots,p-1\}$$ forms a group under multiplication modulo $p$.
• This group has exactly $p-1$ elements.

Important facts:

• Multiplying two nonzero residues gives another nonzero residue.
• Repeated multiplication (powers) stays inside this set.
• The structure is cyclic — meaning it has a generator — and that generator is a primitive root.

What It Means to “Generate” All Nonzero Residues

To “generate” all nonzero residues means:

• Start with some integer $g$.
• Compute $$g^1, g^2, g^3, \dots \pmod p.$$
• If these powers eventually produce every number from $1$ to $p-1$, then $g$ is a primitive root.

In other words:

• The powers of $g$ “walk through” the entire multiplicative world modulo $p$.
• No repeats until you’ve seen all residues.

This is similar to how:

• $1, 2, 4, 8, 16, \dots$ cycles through powers of $2$ in ordinary arithmetic.
• But modulo $p$, the cycle wraps around and can cover everything.

Definition of a Primitive Root (Using Order)

For a prime $p$:

• The order of $g$ modulo $p$ is the smallest positive integer $k$ such that $$g^k \equiv 1 \pmod p.$$

Definition:
An integer $g$ is a primitive root modulo $p$ if its order is exactly $p-1$.

Why $p-1$?

• Because there are $p-1$ nonzero residues.
• If the order is $p-1$, the powers of $g$ must hit all of them.

Small Examples to Build Intuition

Example 1: Primitive roots modulo $7$

Compute powers of $3$:

• $3^1 \equiv 3$
• $3^2 \equiv 2$
• $3^3 \equiv 6$
• $3^4 \equiv 4$
• $3^5 \equiv 5$
• $3^6 \equiv 1$

We saw all residues $1$–$6$, so $3$ is a primitive root mod $7$.

Example 2: A non‑example

Try $2$ modulo $7$:

• $2^1 \equiv 2$
• $2^2 \equiv 4$
• $2^3 \equiv 1$

The order is $3$, not $6$, so $2$ is not a primitive root.

How Many Primitive Roots Does a Prime Have?

A prime $p$ always has primitive roots — in fact, more than one.

Facts:

• The number of primitive roots modulo $p$ is $\varphi(p-1)$.
• Here $\varphi$ is Euler’s totient function.
• Example:
  • For $p=7$, $p-1=6$, and $\varphi(6)=2$.
  • The primitive roots mod $7$ are $3$ and $5$.

Interpretation:

• Primitive roots are not rare.
• But they are “special” — only a fraction of numbers have full order.

Testing Whether an Integer Is a Primitive Root (Practical Method)

To test whether $g$ is a primitive root modulo $p$:

1. Factor $p-1$ into primes: $$p-1 = q_1^{e_1} q_2^{e_2} \cdots q_k^{e_k}.$$
2. For each distinct prime factor $q_i$, compute $$g^{(p-1)/q_i} \pmod p.$$
3. If none of these values is $1$, then $g$ is a primitive root.

Why this works:

• If $g$ had smaller order, that order would divide $p-1$.
• One of these exponent tests would reveal it.

This is the standard practical test used in cryptography.

Note

• This test applies when $p$ is prime
  • because in that case the multiplicative group modulo $p$ is cyclic of order $p-1$.
• For general moduli $n$, the analogous test uses $\varphi(n)$ instead of $p-1$,
  • and primitive roots exist only for $n = 1, 2, 4, p^k, 2p^k$ with $p$ odd prime.

Finding Primitive Roots Efficiently

Strategies:

• Trial and error with the test above.
• Start with small integers: $2,3,4,\dots$.
• For many primes, $2$ or $3$ is already a primitive root.
• Use the fact that:
  • If $g$ is a primitive root, then $g^k$ is also a primitive root iff $\gcd(k,p-1)=1$.

Tips for beginners:

• Always factor $p-1$ first.
• Keep a small table of powers to avoid recomputing.
• Use modular exponentiation to speed things up.

Which Numbers Have Primitive Roots?

Primitive roots do not exist for every modulus.
They exist for all primes, but only for certain composite numbers.
This section gives a simple, memorable rule your readers can rely on.

The Complete Classification

A modulus $ n $ has primitive roots if and only if it is one of the following types:

• $n = 2$
• $n = 4$
• $n = p^k$ where $p$ is an odd prime
• $n = 2p^k$ where $p$ is an odd prime

Why This Matters

Primitive roots are generators of the multiplicative group modulo $n$.
That group is cyclic only for the moduli listed above.

So:

• If the multiplicative group modulo $n$ is cyclic → primitive roots exist.
• If the group is not cyclic → primitive roots do not exist.

This is a deep theorem, but the classification itself is easy to use.

Examples of Moduli That Have Primitive Roots

Powers of odd primes

• $3, 9, 27, 81, \dots$
• $5, 25, 125, \dots$
• $7, 49, 343, \dots$

Twice a power of an odd prime

• $2\cdot 3 = 6$
• $2\cdot 3^2 = 18$
• $2\cdot 5 = 10$
• $2\cdot 5^2 = 50$

The special small cases

• $2$
• $4$

All of these have primitive roots.

Examples of Moduli That Do Not Have Primitive Roots

These fail the classification:

• Any modulus with two different odd prime factors
  • e.g., $15 = 3\cdot 5$, $21 = 3\cdot 7$, $33 = 3\cdot 11$
• Any modulus divisible by $8$
  • e.g., $8, 16, 24, 40, 72$
• Any modulus of the form
  • $4p$ where $p$ is odd
  • e.g., $12, 20, 28, 44$

These moduli have multiplicative groups that are not cyclic, so primitive roots cannot exist.

Applications in Cryptography and Randomness

Primitive roots appear in many modern algorithms:

Cryptography

• Diffie–Hellman key exchange uses a primitive root $g$ modulo a large prime $p$.
• Discrete logarithm problem relies on the difficulty of solving $$g^x \equiv h \pmod p.$$

Randomness and pseudorandom generators

• Some generators use powers of a primitive root to produce sequences that “look random”.

Number theory

• They simplify proofs about modular arithmetic.
• They allow us to express every nonzero residue as a power of a single number.

Common Mistakes and Misunderstandings

Beginners often stumble on:

• Confusing “order” with “primitive root”
  • Order is a property of any integer.
  • Primitive roots are those with maximum order.
• Thinking primitive roots exist for all moduli
  • They exist for primes and for certain special composite numbers, but not all.
• Forgetting to check *all* prime factors of $p-1$
  • Missing even one factor can give a false positive.
• Assuming $g$ must be small
  • Any residue could be a primitive root.

Summary and Key Ideas

• The nonzero residues modulo a prime form a multiplicative group of size $p-1$.
• A primitive root is an integer whose powers generate all these residues.
• The order of a primitive root is exactly $p-1$.
• Primitive roots always exist for primes.
• They are essential in modern cryptography and many number‑theoretic algorithms.

Calculator

Exercises

1. Compute powers: List the powers of $3$ modulo $11$ until they repeat.
   Does $3$ generate all nonzero residues?

   Solution

   Compute powers of $3$ modulo $11$

   We compute:

   • $3^1 \equiv 3 \pmod{11}$
   • $3^2 \equiv 9 \pmod{11}$
   • $3^3 \equiv 27 \equiv 5 \pmod{11}$
   • $3^4 \equiv 3\cdot 5 = 15 \equiv 4 \pmod{11}$
   • $3^5 \equiv 3\cdot 4 = 12 \equiv 1 \pmod{11}$

   So the powers are: $$3, 9, 5, 4, 1.$$

   • Nonzero residues modulo $11$ are $1,2,3,4,5,6,7,8,9,10$.
   • Powers of $3$ gave only $\{1,3,4,5,9\}$.

   Conclusion: $3$ does not generate all nonzero residues modulo $11$, so it is not a primitive root.

2. Find a primitive root: Find at least one primitive root modulo $13$.

   Solution

   Find a primitive root modulo $13$

   We test small candidates.

   Nonzero residues modulo $13$ are $1,\dots,12$, so a primitive root must have order $12$.

   Try $g=2$:

   • $2^1 \equiv 2$
   • $2^2 \equiv 4$
   • $2^3 \equiv 8$
   • $2^4 \equiv 16 \equiv 3$
   • $2^5 \equiv 2\cdot 3 = 6$
   • $2^6 \equiv 2\cdot 6 = 12$
   • $2^7 \equiv 2\cdot 12 = 24 \equiv 11$
   • $2^8 \equiv 2\cdot 11 = 22 \equiv 9$
   • $2^9 \equiv 2\cdot 9 = 18 \equiv 5$
   • $2^{10} \equiv 2\cdot 5 = 10$
   • $2^{11} \equiv 2\cdot 10 = 20 \equiv 7$
   • $2^{12} \equiv 2\cdot 7 = 14 \equiv 1 \pmod{13}$

   We saw all residues $1$–$12$ before returning to $1$.

   Conclusion: $2$ is a primitive root modulo $13$.

3. Test a candidate: Determine whether $2$ is a primitive root modulo $17$.

   Solution

   Determine whether $2$ is a primitive root modulo $17$

   We want to know if the order of $2$ modulo $17$ is $16$.

   A quicker way: factor $16$.

   • $16 = 2^4$.
   • The proper divisors are $1,2,4,8$.
   • We check whether $2^d \equiv 1 \pmod{17}$ for any $d \in \{1,2,4,8\}$.

   Compute:

   • $2^1 \equiv 2 \not\equiv 1$
   • $2^2 \equiv 4 \not\equiv 1$
   • $2^4 \equiv 16 \not\equiv 1$
   • $2^8 \equiv 16^2 \equiv 256 \equiv 256 - 238 = 18 \equiv 1 \pmod{17}$
     (since $17\cdot 14 = 238$)

   So $2^8 \equiv 1 \pmod{17}$, and $8 < 16$.

   Conclusion: the order of $2$ modulo $17$ is $8$, so $2$ is not a primitive root modulo $17$.

4. Count primitive roots: How many primitive roots does $p=19$ have?
   (Hint: compute $\varphi(18)$.)

   Solution

   How many primitive roots does $p=19$ have?

   We use the fact:

   • Number of primitive roots modulo a prime $p$ is $\varphi(p-1)$.

   Here:

   • $p = 19$
   • $p-1 = 18 = 2 \cdot 3^2$

   Compute $\varphi(18)$:

   • $\varphi(18) = 18\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)$
   • $\varphi(18) = 18 \cdot \frac{1}{2} \cdot \frac{2}{3} = 18 \cdot \frac{1}{3} = 6$

   Conclusion: there are $6$ primitive roots modulo $19$.

5. Order practice: Find the order of $4$ modulo $11$.
   Is it a primitive root?

   Solution

   Find the order of $4$ modulo $11$. Is it a primitive root?

   We want the smallest positive $k$ such that $4^k \equiv 1 \pmod{11}$.

   Compute powers:

   • $4^1 \equiv 4$
   • $4^2 \equiv 16 \equiv 5$
   • $4^3 \equiv 4\cdot 5 = 20 \equiv 9$
   • $4^4 \equiv 4\cdot 9 = 36 \equiv 3$
   • $4^5 \equiv 4\cdot 3 = 12 \equiv 1 \pmod{11}$

   So the order of $4$ modulo $11$ is $5$.

   • Nonzero residues modulo $11$ are $1,\dots,10$, so a primitive root would need order $10$.

   Conclusion: $4$ is not a primitive root modulo $11$.

6. Factor‑based test: Use the prime factorization of $p-1$ to test whether $6$ is a primitive root modulo $13$.

   Solution

   Use factorization of $p-1$ to test whether $6$ is a primitive root modulo $13$

   We use the standard test:

   • $p = 13$, so $p-1 = 12$.
   • Factor $12$: $$12 = 2^2 \cdot 3.$$
   • Distinct prime factors: $2$ and $3$.

   We must check:

   • $6^{12/2} = 6^6 \pmod{13}$
   • $6^{12/3} = 6^4 \pmod{13}$

   If neither is $1$, then $6$ is a primitive root.

   Compute step by step:

   • $6^2 \equiv 36 \equiv 10 \pmod{13}$
   • $6^4 \equiv (6^2)^2 \equiv 10^2 = 100 \equiv 100 - 91 = 9 \pmod{13}$
     (so $6^4 \not\equiv 1$)

   Now $6^6 = 6^4 \cdot 6^2$:

   • $6^6 \equiv 9 \cdot 10 = 90 \equiv 90 - 78 = 12 \pmod{13}$
     (so $6^6 \not\equiv 1$)

   Neither $6^4$ nor $6^6$ is $1$ modulo $13$.

   Conclusion: $6$ is a primitive root modulo $13$.

7. Challenge: Show that if $g$ is a primitive root modulo $p$, then $g^k$ is also a primitive root iff $\gcd(k,p-1)=1$.

   Solution

   Show: if $g$ is a primitive root modulo $p$, then $g^k$ is a primitive root iff $\gcd(k,p-1)=1$

   Let $p$ be prime and $g$ a primitive root modulo $p$.

   • So the order of $g$ is $p-1$.

   Consider $h = g^k$.

   • The order of $h$ (call it $\text{ord}(h)$) must divide $p-1$.
   • There is a standard fact from group theory (which you may have already introduced or can state without proof): $$\text{ord}(g^k) = \frac{p-1}{\gcd(k,p-1)}.$$

   Now:

   • $h$ is a primitive root iff its order is $p-1$.
   • That is, we need $$\frac{p-1}{\gcd(k,p-1)} = p-1.$$
   • This happens exactly when $\gcd(k,p-1) = 1$.

   So:

   • If $\gcd(k,p-1) = 1$, then $\text{ord}(g^k) = p-1$, so $g^k$ is a primitive root.
   • If $\gcd(k,p-1) \neq 1$, then $\text{ord}(g^k) < p-1$, so $g^k$ is not a primitive root.

   Conclusion: $g^k$ is a primitive root modulo $p$ iff $\gcd(k,p-1)=1$.

8. Application question: Explain why primitive roots are useful in cryptography.

   Solution

   Explain why primitive roots are useful in cryptography

   Key points you might mention:

   • Generators of a large cyclic group:
     Primitive roots generate all nonzero residues modulo a prime $p$. This gives a large cyclic group of size $p-1$.
   • Discrete logarithm problem:
     If $g$ is a primitive root modulo $p$, then every nonzero residue $h$ can be written as $g^x \pmod{p}$ for some $x$.
     • Finding $h$ from $x$ (computing $g^x$) is easy.
     • Finding $x$ from $h$ (solving $g^x \equiv h \pmod{p}$) is believed to be hard for large $p$.
   • Security of protocols:
     Many cryptographic protocols (like Diffie–Hellman) rely on the difficulty of the discrete logarithm problem in such groups.
     Primitive roots ensure the group is as large and “uniform” as possible, which is good for security.